package com.Offer;


import com.pojo.ListNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/*
    面试题6：从尾到头打印链表
    题目描述：输入一个链表，从尾到头打印链表每个节点的值。
    测试用例：1,2,3,4,5,6,7
 */
public class demo6 {

    public static void main(String[] args) {
        int[] input=new int[]{1,2,3,4,5,6,7};
        ListNode first = new ListNode(input[0]);
        for(int i =1;i<input.length;i++){
            first.add(input[i]);
        }

        //创建链表数据方法二
/*        ListNode first = null,last = null,newNode;
        for(int i = 0;i<input.length;i++){
            newNode = new ListNode(input[i]);
            newNode.next = null;
            if(first == null){
                first = newNode;
                last = newNode;
            }else{
                last.next = newNode;
                last = newNode;
            }
        }
        */
        //方法一的输出
        ArrayList<Integer> list1 = printListFromTailToHead(first);
        for(int a:list1){
            System.out.print(a+" ");
        }

        System.out.println();

        //方法二的输出
        ArrayList<Integer> list2 = printListReverse2(first);
        for(int a:list2){
            System.out.print(a+" ");
        }
    }

    //方法一:用栈，将链表全部压入栈中后再输出
    public static ArrayList<Integer> printListFromTailToHead(ListNode headNode){
        if(headNode == null){
            return new ArrayList<Integer>();
        }
        Stack<ListNode> stack = new Stack<ListNode>();
        while(headNode != null){
            stack.push(headNode);
            headNode = headNode.next;
        }
        ArrayList<Integer> list = new ArrayList<Integer>();
        while(!stack.isEmpty()){
            list.add(stack.pop().val);
        }
        return list;
    }
    //方法二:递归
    public static ArrayList<Integer> printListReverse2(ListNode listNode){
        ArrayList<Integer> list = new ArrayList<Integer>();

        if(listNode != null){
            if(listNode.next != null){
                list = printListReverse2(listNode.next);
            }
            list.add(listNode.val);
        }
        return list;
    }
}
